//题目:
// 给定一个三角形 triangle ，找出自顶向下的最小路径和。
// 每一步只能移动到下一行中相邻的结点上。
// 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
// 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

// 示例 1：
// 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
// 输出：11
// 解释：如下面简图所示：
//    2
//   3 4
//  6 5 7
// 4 1 8 3
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

// 示例 2：
// 输入：triangle = [[-10]]
// 输出：-10
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        int m=triangle.size(),n=triangle.back().size();
        //1.创建dp表————dp[i][j]表示：从顶点来到(i,j)位置的最小路径和
        vector<vector<int>> dp(m+1,vector<int>(n+1,0xffffff));
        //2.初始化
        dp[0][0]=0;
        for(int i=1;i<=m;i++) dp[i][0]=dp[i-1][0]+triangle[i-1][0];
        //3.填表————动态转移方程：dp[i][j]=t[i][j]+min(dp[i-1][j],dp[i-1][j-1])
        for(int i=1;i<=m;i++)
            for(int j=1;j<=i;j++)
                dp[i][j]=triangle[i-1][j-1]+min(dp[i-1][j],dp[i-1][j-1]);
        //4.确定返回值
        int ret=dp[m][0];
        for(int j=1;j<=n;j++) ret=min(ret,dp[m][j]);
        return ret;
    }
};